package org.example.myleet.segmenttree;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.Parser;

import java.util.ArrayList;
import java.util.List;

public class SegmentTreeSolution {
    /**
     * 715【线段树】Range 模块
     */
    static class RangeModule {

        private static final int TRACKED = -1;
        private static final int UNTRACKED = 1;

        SegmentTree segmentTree;

        public RangeModule() {
            segmentTree = new DynamicSplitSegmentTree(1, 1000000000);
            segmentTree.modify(1, 1000000000, UNTRACKED, null);
        }

        /**
         * 根据题目设定，查询区间如果包含未被跟踪的部分则查询结果为false
         * 可以设定为add的modify为设定区间为-1，remove的modify设定区间为1
         * 如果查询结果为1，说明有实数点未被跟踪，如果为-1则全被跟踪
         */
        public void addRange(int left, int right) {
            segmentTree.modify(left, right - 1, TRACKED, null);
        }

        public boolean queryRange(int left, int right) {
            int maxVal = segmentTree.query(left, right - 1, null);
            return maxVal < UNTRACKED;
        }

        public void removeRange(int left, int right) {
            segmentTree.modify(left, right - 1, UNTRACKED, null);
        }

        static class DynamicSplitSegmentTree implements SegmentTree {
            Segment root;

            /**
             * 定义线段树控制的范围
             * @param leftBorder 范围的左端点
             * @param rightBorder 范围的右端点
             */
            public DynamicSplitSegmentTree(int leftBorder, int rightBorder) {
                root = new Segment(leftBorder, rightBorder);
            }

            @Override
            public void modify(int l, int r, int v, Segment segment) {
                if (l > r) {
                    return;
                }
                if (null == segment) {
                    segment = root;
                }
                if (l <= segment.l && segment.r <= r) {
                    //更新的范围覆盖了整个线段，则直接修改线段的值，并标记add标签
                    segment.v = v;
                    segment.add = v;
                    return;
                }
                //更新的范围没有覆盖到整个线段，此时需要根据更新范围对应更新线段的左节点和右节点的值
                pushDown(segment);
                if (l <= segment.mid) {
                    //更新范围覆盖到左节点，修改左节点的值
                    modify(l, r, v, segment.left);
                }
                if (r > segment.mid) {
                    //更新范围覆盖到右节点，修改左右点的值
                    modify(l, r, v, segment.right);
                }
                //根据左节点和右节点的值更新本范围内的值
                pushUp(segment);
            }

            /**
             * 查询区间中的最大值
             */
            @Override
            public int query(int l, int r, Segment segment) {
                if (l > r) {
                    return 0;
                }
                if (null == segment) {
                    segment = root;
                }
                if (l <= segment.l && segment.r <= r) {
                    //查询的范围覆盖了整个线段，则查询结果为线段的值
                    return segment.v;
                }
                //查询的范围没有覆盖到整个线段，此时需要根据线段的左节点和右节点的值确定查询范围的结果
                pushDown(segment);
                int v = 0;
                if (l <= segment.mid) {
                    //查询范围覆盖到左节点
                    v = Math.max(v, query(l, r, segment.left));
                }
                if (r > segment.mid) {
                    //查询范围覆盖到右节点
                    v = Math.max(v, query(l, r, segment.right));
                }
                return v;
            }

            @Override
            public void pushDown(Segment segment) {
                if (segment.l == segment.r) {
                    //已经是叶子节点，无需继续劈开范围
                    return;
                }
                if (null == segment.left) {
                    segment.left = new Segment(segment.l, segment.mid);
                }
                if (null == segment.right) {
                    segment.right = new Segment(segment.mid + 1, segment.r);
                }
                if (0 != segment.add) {
                    //存在线段范围内的值需要更新，则传递到子节点上
                    segment.left.v = segment.add;
                    segment.right.v = segment.add;
                    segment.left.add = segment.add;
                    segment.right.add = segment.add;
                    //传递完成，线段的值更新标签归零
                    segment.add = 0;
                }
            }

            @Override
            public void pushUp(Segment segment) {
                //根据题意，线段的值取线段范围内的最大值
                segment.v = Math.max(segment.left.v, segment.right.v);
            }
        }
    }

    //p729
    static class MyCalendar2 {
        private static final int BOOKED = 1;

        private SegmentTree segmentTree;

        public MyCalendar2() {
            segmentTree = new DynamicSplitSegmentTree(0, 1000000000);
        }

        public boolean book(int start, int end) {
            int value = segmentTree.query(start, end - 1, null);
            if (value == BOOKED) {
                return false;
            }
            segmentTree.modify(start, end - 1, BOOKED, null);
            return true;
        }
    }

    //p2569
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        DynamicSplitSegmentTreeFor2569 segmentTree = new DynamicSplitSegmentTreeFor2569(nums1);
        long sum2 = 0L;
        for (int num : nums2) {
            sum2 += num;
        }
        List<Long> answer = new ArrayList<>();
        for (int[] query : queries) {
            if (query[0] == 1) {
                segmentTree.modify(query[1], query[2], 0, segmentTree.getRoot());
            } else if (query[0] == 2) {
                sum2 += (long) segmentTree.getRoot().v * query[1];
            } else {
                answer.add(sum2);
            }
        }
        long[] ret = new long[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            ret[i] = answer.get(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        SegmentTreeSolution solution = new SegmentTreeSolution();
        Assert.isTrue("[689,920]".equals(JsonUtils.toJson(solution.handleQuery(new int[]{0,0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,0,0,0,1,1,1}, new int[]{30,46,43,34,39,16,14,41,22,11,32,2,44,12,22,36,44,49,50,10,33,7,42},Parser.parse("[[2,1,0],[3,0,0],[1,15,21],[2,21,0],[3,0,0]]")))));
        Assert.isTrue("[3]".equals(JsonUtils.toJson(solution.handleQuery(new int[]{0,1,0,1,0}, new int[]{0,0,0,0,0},Parser.parse("[[1,2,4],[2,1,0],[3,0,0]]")))));
        Assert.isTrue("[679,679,1053]".equals(JsonUtils.toJson(solution.handleQuery(new int[]{0,0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,0,0,0,1,1,1}, new int[]{30,46,43,34,39,16,14,41,22,11,32,2,44,12,22,36,44,49,50,10,33,7,42},Parser.parse("[[1,15,21],[3,0,0],[3,0,0],[2,21,0],[2,13,0],[3,0,0]]")))));
        Assert.isTrue("[5]".equals(JsonUtils.toJson(solution.handleQuery(new int[]{1}, new int[]{5},Parser.parse("[[2,0,0],[3,0,0]]")))));
        Assert.isTrue("[3]".equals(JsonUtils.toJson(solution.handleQuery(new int[]{1,0,1}, new int[]{0,0,0},Parser.parse("[[1,1,1],[2,1,0],[3,0,0]]")))));
    }
}
